

// 逆序对的数量
// 归并 + 排序
// [4 7 8]  [2 3 7]
// 如果4比2大的话，那么7 8也一定比2大，所以判断出4比2大，就可以把4放入排序数组，逆序对增加mid - left + 1个了


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int tmp[50000];
    int reversePairs(vector<int>& record) {
        if(record.size() <= 1)
            return 0;

        return _reversePairs(record, 0, record.size() - 1);
    }
    
    int _reversePairs(vector<int>& record, int left, int right)
    {
        if(left >= right)
            return 0;
        
        //该区间逆序对的数量
        int ret = 0;
        //递归
        int mid = (right - left) / 2 + left;
        ret += _reversePairs(record, left, mid);
        ret += _reversePairs(record, mid + 1, right);

        //排序 + 统计逆序对数量
        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right)
        {
            //如果左面元素，比右面元素小
            if(record[i] <= record[j])
            {
                tmp[k++] = record[i++];
            }
            else
            {
                //更新逆序对数量
                ret += (mid - i + 1);
                tmp[k++] = record[j++];
            }
        }
        while(i <= mid) tmp[k++] = record[i++];
        while(j <= right) tmp[k++] = record[j++];

        //将排序好的临时数组更新回原数组
        for(int l = left; l <= right; l++)
        {
            record[l] = tmp[l -left];
        }
        //返回该区间的逆序对数量
        return ret;
    }
};